package com.leetcode.algs4.sort;

import java.util.Arrays;

/**
 * @author Dennis Li
 * @date 2020/6/14 19:02
 */
public class MergeSort {

    private static int[] aux;

    public static void main(String[] args) {
        int[] arr = {-9, 78, 0, 23, -567, 70};
        aux = new int[arr.length];
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr, int lo, int hi) {
        if (lo >= hi) return;
        int mid = (lo + hi) / 2;
        // 自顶向下进行归并
        sort(arr, lo, mid);
        sort(arr, mid + 1, hi);
        merge(arr, lo, mid, hi);
    }

    public static void merge(int[] arr, int lo, int mid, int hi) {
        int k = lo, j = mid + 1;

        // 复制数组
        if (hi + 1 - lo >= 0)
            System.arraycopy(arr, lo, aux, lo, hi + 1 - lo);

        for (int i = lo; i <= hi; i++) {
            // 都是从左至右的
            if (k > mid) arr[i] = aux[j++];
            else if (j > hi) arr[i] = aux[k++];
                // 如果右边的比左边小，则交换位置
            else if (aux[k] > aux[j]) arr[i] = aux[j++];
                // 如果左边的
            else arr[i] = aux[k++];
        }
    }
}
